package cn.leetcode.easy;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 题目：最大公共前缀
 * 描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
 * 示例 1：
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 示例 2：
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 *
 * @author dunlingzi
 */
public class MaximumPublicPrefix {

    /**
     * 暴力破解方式
     */
    public String longestCommonPrefix(String[] strs) {
        // 新建一个列表存储公共前缀字符
        // 循环第一个字符串的
        // 循环字符串数组
        // 采用双层循环   n平方
        // 将数组拆成字符串
        // 核心是 公共前缀，所以必循从首字母开始
        String str = strs[0];
        if (strs.length == 1) {
            return str;
        }
        if (Objects.equals(str, "")) {
            return "";
        }
        boolean isBreak = false;
        char[] first = str.toCharArray();
        // 保存最大公共前缀字符
        List<Character> common = new ArrayList<>();
        // 遍历第一个字符串的字符
        for (int i = 0; i < first.length; i++) {
            if (isBreak) {
                break;
            }
            char x = first[i];
            // 从第二个开始遍历字符串数组
            for (int j = 1; j < strs.length; j++) {
                String string = strs[j];
                // 中间出现空串直接返回空串
                if (Objects.equals(string, "")) {
                    common.clear();
                    isBreak = true;
                    break;
                }
                char[] other = string.toCharArray();
                if (i >= other.length) {
                    isBreak = true;
                    break;
                }
                char y = other[i];
                if (x != y) {
                    isBreak = true;
                    break;
                }
            }
            if (!isBreak) {
                common.add(x);
            }

        }
        StringBuilder stringBuilder = new StringBuilder();
        common.forEach(stringBuilder::append);

        return stringBuilder.toString();
    }

    /**
     * 横向对比
     * 1、S1与S2获取公共前缀
     * 2、将获取的公共前缀与S3再获取公共前缀，知道Sn
     */
    public String longestCommonPrefixConquer(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = commonPrefix(prefix, strs[i]);
            if (Objects.equals(prefix, "")) {
                break;
            }
        }
        return prefix;
    }

    /**
     * 获取A、B字符串的公共前缀
     *
     * @param strA 字符串A
     * @param strB 字符串B
     * @return 公共前缀
     */
    public String commonPrefix(String strA, String strB) {
        int length = Math.min(strA.length(), strB.length());
        int index = 0;
        while (index < length && strA.charAt(index) == strB.charAt(index)) {
            index++;
        }
        return strA.substring(0, index);
    }
}
